<HTML>
<BODY>
<p>Linear Algebraic matrix computations operating on {@link cern.colt.matrix.DoubleMatrix2D} 
  and {@link cern.colt.matrix.DoubleMatrix1D}. </p>
<h1><a name="Overview"></a>Overview</h1>
<p>The linalg package provides easy and performant access to compute intensive 
  Linear Algebra. Much functionality is concentrated in class {@link cern.colt.matrix.linalg.Algebra}. 
  Five fundamental matrix decompositions, which consist of pairs or triples of 
  matrices, permutation vectors, and the like, produce results in five decomposition 
  classes.&nbsp; These decompositions are accessed by the <tt>Algebra</tt> class 
  to compute solutions of simultaneous linear equations, determinants, inverses 
  and other matrix functions.&nbsp; The five decompositions are </p>
<ul>
  <li> Cholesky Decomposition of symmetric, positive definite matrices</li>
  <li> LU Decomposition (Gaussian elimination) of rectangular matrices</li>
  <li> QR Decomposition of rectangular matrices</li>
  <li> Eigenvalue Decomposition of both symmetric and nonsymmetric square matrices</li>
  <li> Singular Value Decomposition of rectangular matrices</li>
</ul>
<h1>Colt and Jama</h1>
<p>This package could only be rolled out easily because it is to a large degree 
  adapted from interfaces and implementations of the Jama matrix package. See 
  the <a href="http://math.nist.gov/javanumerics/jama">Jama homepage</a>. Due 
  credit is given to Joe Hicklin, Cleve Moler, Peter Webb, Ronald F. Boisvert, 
  Bruce Miller, Roldan Pozo and Karin Remington, the Jama authors from <a href="http://www.mathworks.com/">MathWorks</a> 
  and <a
href="http://www.nist.gov/">NIST</a>.</p>
<h2>Design Issues</h2>
<p> Jama matrices are of type <tt>Jama.Matrix</tt>, Colt matrices of type <tt>cern.colt.matrix.DoubleMatrix1D</tt>, 
  <tt>cern.colt.matrix.DoubleMatrix2D</tt> and <tt>cern.colt.matrix.DoubleMatrix3D</tt>. 
<p><tt>Jama.Matrix</tt> is not a general-purpose array class. It is designed for 
  a single special purpose: Linear algebra. Because of its limited scope, Jama 
  can combine data structure and algorithms in a class <tt>Jama.Matrix</tt>. In 
  contrast, Colt matrices are general-purpose array classes. Since multi-dimensional 
  matrices (arrays) have many applications, of which only one is linear algebra, 
  Colt matrix packages are designed to avoid fat interfaces, yet allow to form 
  the basis on top of which a broad set of functionality and applications can 
  be defined (a similar spirit is used in STL and IBM <a href="http://math.nist.gov/javanumerics/array/"> 
  Array</a>). Thus, data structure and special-purpose algorithms are separated. 
  Class <tt>Algebra</tt> works on <tt>DoubleMatrix2D </tt>and contains the operations 
  of <tt>Jama.Matrix</tt>, but holds no data structure. Class <tt>DoubleMatrix2D</tt> 
  contains an efficient and flexible multi-dimensional array data structure, as 
  well as multi-purpose operations, but (almost) no linear algebraic operations. 
<p>As a consequence a Colt user initially faces some additional complexity, but 
  after getting used to such a design, will honour the fact that logically related 
  functionality is logically separated. For example, if a user is not interested 
  in Formatting, Sorting, Partitioning, Statistics, etc. he/she does not see this 
  functionality, because it is neither defined in the linalg package nor the matrix 
  package, but somewhere else. 
<p>Perhaps more importantly, such a design will scale over time, as more and more 
  functionality from many scientific and engineering domains is added. Also see 
  <a href="../package-summary.html#Algorithms">matrix algorithms</a>. 
<h2> Functionality</h2>
<p>All methods of <tt>Jama.Matrix</tt> are provided in <tt>Algebra</tt>, except 
  for some less important convenience methods. Colt matrices (similar to IBM Arrays) 
  are powerful and flexible data structures. Subrange, slice, dice, flip, selection 
  and sort views are available for Colt matrices, but not for Jama matrices. (They 
  are difficult to implement <i>efficiently</i> with Jama matrices, because they 
  internally use <tt>double[][]</tt> arrays). 
<h2>Performance</h2>
<p>No extensive performance studies have been carried out so far.<br>
  Jama matrices weakly encapsulate a normal <tt>double[][]</tt> array. Dense Colt 
  matrices strongly encapsulate a <tt>double[]</tt> array and use some arithmetic 
  to address cells in 2-d. Addressing a cell is more expensive using <tt>double[][]</tt> 
  arrays, due to bounds-checking, null pointer checks, non-contigous memory, and 
  problems that compilers have to optimize such code. Using <tt>double[]</tt> 
  arrays less bounds-checking, less null pointer checks, better cache locality 
  and better compiler optimizations can be seen, often eliminating bounds-checking 
  and null-pointer checks, paving the way for effective pipelining. See the publications 
  of IBM Watson's <a href="http://www.research.ibm.com/ninja/">Ninja project</a>.
<p>To improve performance, matrix computations should use highly optimized kernels 
  in innermost loops. These kernels are not part of class <tt>Algebra</tt>, but 
  part of <tt>DoubleMatrix2D</tt> and <tt>DoubleMatrix1D</tt>. Otherwise they 
  couldn't be fully optimized. For example, with some arithmetic (not exposed 
  to a user), a loop over a 1-d or 2-d matrix can internally reduce cell adressing 
  overhead. Some of the most critical types of (innermost) loop operations have 
  a corresponding optimized method in <tt>DoubleMatrix2D</tt> and <tt>DoubleMatrix1D</tt>. 
  For example, dot products, multiplications, <tt>assign(function)</tt> transforms 
  and <tt>aggregate</tt> methods are such internally specialized kernels. Feedback 
  may result in a few more optimized kernels. Thus, in the name of performance, 
  in a few cases, algorithms and data structure are not completely separeted.
<p>Some internal optimizations have been introduced, in particular for multiplications, 
  the LU-Decomposition and the Cholesky-Decomposition. The other decomposition 
  classes are almost identical to the corresponding Jama classes - as such they 
  are functional but not (yet) particularly efficient. 
<p>For small matrices, you may be better off using Sun's Java 3D 1.2, see <a href="http://java.sun.com/products/java-media/3D/1_2_api/j3dguide/AppendixMath.doc.html#47281">javax.vecmath 
  - spec</a> and <a href="http://java.sun.com/products/java-media/3D/1_2_api/j3dapi/javax/vecmath/package-summary.html">javax.vecmath 
  javadoc</a>.
<p><br>
<h2>Volunteers</h2>
<p align="left"> <i> We are looking for volunteers! <br>
  Do you have a background in Matrix Computations?<br>
  </i><i>Do you care about performance and usability? <br>
  Are you enthusiastic about Open Source? <br>
  With your help, this package could become better and richer!<br>
  Contact <a href="mailto:wolfgang.hoschek@cern.ch">wolfgang.hoschek@cern.ch</a> 
  for more info.</i> </p>
</BODY>
</HTML>